package Algorithm.dfs;

import DataStructure.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 872. 叶子相似的树 https://leetcode.cn/problems/leaf-similar-trees
 */
public class LeafSimilar {

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> leaf1 = new ArrayList<Integer>();
        List<Integer> leaf2 = new ArrayList<Integer>();
        preOrder(root1, leaf1);
        preOrder(root2, leaf2);
        if(leaf1.size() !=  leaf2.size()) return false;
        for(int i = 0;i < leaf1.size();i++) {
            if(leaf1.get(i) != leaf2.get(i))
                return false;
        }
        return true;
    }

    public List<Integer> preOrder(TreeNode root, List<Integer> leafList) {
        if(root == null) return leafList;
        if(root.left == null && root.right == null) leafList.add(root.val);
        preOrder(root.left, leafList);
        preOrder(root.right, leafList);
        return leafList;
    }
}
